{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Repeated Substring Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: repeatedSubstringPattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重复的子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空的字符串<meta charset=\"UTF-8\" />&nbsp;<code>s</code>&nbsp;，检查是否可以通过由它的一个子串重复多次构成。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abab\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 可由子串 \"ab\" 重复两次构成。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aba\"\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abcabcabcabc\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 可由子串 \"abc\" 重复四次构成。 (或子串 \"abcabc\" 重复两次构成。)\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [repeated-substring-pattern](https://leetcode.cn/problems/repeated-substring-pattern/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [repeated-substring-pattern](https://leetcode.cn/problems/repeated-substring-pattern/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abab\"', '\"aba\"', '\"abcabcabcabc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        s_tmp = s\n",
    "        for i in range(len(s)//2):\n",
    "            s_tmp = s_tmp[1:]+s_tmp[0]\n",
    "            if s_tmp == s:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n<=1:\n",
    "            return False\n",
    "        else:\n",
    "            ss = s[1:] + s[:-1]\n",
    "            if ss.find(s) >= 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "      return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        ss=s[1:]+s[:-1]\n",
    "        return s in ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        l = len(s)\n",
    "        for n in range(1, l // 2 + 1):\n",
    "            if len(set([s[m:m+n] for m in range(0, l , n)])) == 1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for i in range(1, n//2+1):\n",
    "            if n%i == 0:\n",
    "                s_ = s[:i]\n",
    "                if s_ * (n//i) == s:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        res = s + s\n",
    "        res1 = res[1:-1]\n",
    "        if s in res1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for m in range(1, n//2 + 1):\n",
    "            if n % m != 0: continue\n",
    "            for j in range(n-m):\n",
    "                if s[j] != s[j+m]: break\n",
    "            if s[j] == s[j+m]: return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for i in range(1,n//2+1):\n",
    "            if not n % i:\n",
    "                if s[:i]*(n//i) == s: #从小到大一个个重复看\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for i in range(1, n//2 + 1):\n",
    "            if n % i == 0:\n",
    "                if all(s[j] == s[j - i] for j in range(i, n)):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        ss = s[1:] + s[:-1] \n",
    "        print(ss.find(s))              \n",
    "        return ss.find(s) != -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        s1 = ''\n",
    "        for item in range(length):\n",
    "            s1 = s[0:item+1]\n",
    "            if s1*(length//(item+1)) == s and length / len(s1) >1:\n",
    "                return True\n",
    "            else:\n",
    "                continue\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 1:\n",
    "            return False\n",
    "        len1 = len(s)\n",
    "        for i in range(len1):\n",
    "            if i != 0 and s[i] == s[0]:\n",
    "                if s[0:i] * (len1 //i) == s:\n",
    "                    return True\n",
    "                else:\n",
    "                    continue\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        for i in range(len(s)//2):\n",
    "            if len(s) % (i+1) == 0:\n",
    "                if s[:i+1]*(len(s)//(i+1)) == s:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            if n % i == 0:\n",
    "                if s == s[:i] * (n // i):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def repeatedSubstringPattern(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            if n % i == 0:\n",
    "                if s[:i] * (n // i) == s:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        \n",
    "        for i in range(1,n//2+1):\n",
    "            flag=0\n",
    "            if n%i==0:\n",
    "                flag=1\n",
    "                for j in range(i,n):\n",
    "                    if s[j]==s[j-i]:\n",
    "                        flag*=1\n",
    "                    else:\n",
    "                        flag*=0\n",
    "                        break\n",
    "\n",
    "            if flag==1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 意思就是当s前后链接，假如是有子串构成的话，去头去尾也就是去了两个子串，但是会从中间补上，假如是没有子串，那肯定构不成一个完整的s\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if s in (s + s)[1:-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        tmp = s\n",
    "        s = s + s\n",
    "        s = s[1:-1]\n",
    "        if s.find(tmp) != -1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        res_s = s + s\n",
    "        if res_s.find(s, 1, len(res_s) - 1) != -1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return (s+s).find(s,1)!=len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        for i in range(1,n//2+1):\n",
    "            if n%i==0:\n",
    "                if all(s[j]==s[j-i] for j in range(i,n)):\n",
    "                    return True\n",
    "        else:\n",
    "            return False\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        # i -- 长度\n",
    "        for i in range(1,n//2+1):\n",
    "            if n%i == 0:\n",
    "                if s[:i]*(n//i) == s:\n",
    "                    return True\n",
    "        return False \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def check(substr):\n",
    "            if len(substr) == len(s):\n",
    "                return False\n",
    "            l = len(substr)\n",
    "            if len(s) % l !=0:\n",
    "                return False\n",
    "            ind = 0\n",
    "            while ind+l<=len(s):\n",
    "                if s[ind:ind+l] != s[:l]:\n",
    "                    return False\n",
    "                ind += l\n",
    "            # print(\"sub:\", substr)\n",
    "            return True\n",
    "        for i in range(1,len(s)):\n",
    "            if check(s[:i]):\n",
    "                return True\n",
    "            # print(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "         return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        for i in range(1,n//2+1):\n",
    "            if(n%i==0):\n",
    "                t=s[0:i]\n",
    "                start=0\n",
    "                while(start<n):\n",
    "                    k=0\n",
    "                    while(k<i):\n",
    "                        if(t[k]!=s[start+k]):\n",
    "                            break\n",
    "                        k+=1\n",
    "                    if(k!=i):\n",
    "                        break\n",
    "                    start+=i\n",
    "                if(start==n):\n",
    "                    return True\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        l=len(s);s1=[]\n",
    "        if len(s)==1:\n",
    "            return False\n",
    "        if len(s)==2:\n",
    "            if s[0]!=s[1]:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        for i in s:\n",
    "            if i not in s1:\n",
    "                s1.append(i)\n",
    "        if len(s1)==1:\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(2,ceil(l/2)+1):\n",
    "                m=s[:i]\n",
    "                if l%i==0:\n",
    "                    n=int(l/i)\n",
    "                    if s==m*n:\n",
    "                        return True\n",
    "            if i==ceil(l/2):\n",
    "                return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        sublength = 1\n",
    "        total = len(s)\n",
    "        while sublength <= total // 2:\n",
    "            if total % sublength != 0:\n",
    "                sublength += 1\n",
    "                continue\n",
    "            left = 0 \n",
    "            right = sublength\n",
    "            while right < total:\n",
    "                if s[left] != s[right]:\n",
    "                    break\n",
    "                else:\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "            if right == total:\n",
    "                return True\n",
    "            sublength += 1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNext(self, nxt, s):\n",
    "        j = 0\n",
    "        nxt[0] = 0\n",
    "        for i in range(1, len(s)):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nxt[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next[i] = j\n",
    "        return nxt\n",
    "\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        # s = list(s)\n",
    "        # n = len(s)\n",
    "        # for i in range(2, n // 2, 1):\n",
    "        #     sub_s = s[:i]\n",
    "        #     sub_n = i\n",
    "        #     for j in range(n // i):\n",
    "        #         if sub_s == s[:]:\n",
    "        #             continue\n",
    "        #         else: \n",
    "        #             break\n",
    "        #     if j == (n // i) - 1:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # return False\n",
    "        # 暴力法，好好学！这都不会！\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        \n",
    "        sub_s = \"\"\n",
    "        for i in range(1, n //2 + 1):\n",
    "            if n % i == 0:\n",
    "                sub_s = s[:i]\n",
    "                if sub_s * (n // i) == s:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "        # n = len(s)\n",
    "        # if n == 0:\n",
    "        #     return False\n",
    "\n",
    "        # for i in range(1, n // 2):\n",
    "        #     sub_s = s[:i]\n",
    "        #     # next = [0] * len(sub_s)\n",
    "        #     nxt = [0] * len(s)\n",
    "        #     self.getNext(nxt, sub_s)\n",
    "        #     # j = 0\n",
    "        #     # for i in range(1, len(s)):\n",
    "        #     #     while j > 0 and s[i] != sub_s[j]:\n",
    "        #     #         j = next[j - 1]\n",
    "        #     #     if s[i] == sub_s[j]:\n",
    "        #     #         j += 1\n",
    "        #     #     if j == len(sub_s):\n",
    "        #     # 不需要真的匹配\n",
    "        #     if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:\n",
    "        #             return True\n",
    "        # return False\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        def is_cycle(s,period):\n",
    "            if len(s)==period:\n",
    "                return False\n",
    "            if len(s)%period!=0:\n",
    "                return False\n",
    "            for idx in range(0,period):\n",
    "                c = s[idx]\n",
    "                for j in range(period+idx,length,period):\n",
    "                    if s[j]!=c:\n",
    "                        return False\n",
    "            return True\n",
    "        longest = len(s)//2\n",
    "        for i in range(1,longest+1):\n",
    "            if is_cycle(s,i):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        r = 1\n",
    "        while r < len(s):\n",
    "            for i in range(r, len(s), r):\n",
    "                if s[i:i+r] != s[:r]:\n",
    "                    r += 1\n",
    "                    while len(s) % r != 0:\n",
    "                        r += 1\n",
    "                    break\n",
    "            if i+r == len(s):\n",
    "                return True\n",
    "        return False      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        s0=s+s\n",
    "        for i in range(1,len(s)):\n",
    "            if s0[i:len(s)+i]==s:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return True if s in (s + s)[1:-1] else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        ss = s[1:] + s[:-1]  \n",
    "        #找不到返回-1 找到了返回其索引值           \n",
    "        return ss.find(s) != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        ss = s+s\n",
    "        if s in ss[1:-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        for i in range(1,n//2+1):\n",
    "            if(n%i==0):\n",
    "                t=s[0:i]\n",
    "                start=0\n",
    "                while(start<n):\n",
    "                    k=0\n",
    "                    while(k<i):\n",
    "                        if(t[k]!=s[start+k]):\n",
    "                            break\n",
    "                        k+=1\n",
    "                    if(k!=i):\n",
    "                        break\n",
    "                    start+=i\n",
    "                if(start==n):\n",
    "                    return True\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        l = len(s)\n",
    "        for i in range(1, int(l/2)+1):\n",
    "            if not l%i == 0:\n",
    "                continue\n",
    "            substr = s[:i]\n",
    "            is_repeat = True\n",
    "            for j in range(int(l/i)):\n",
    "                if not s[j*i:(j+1)*i] == substr:\n",
    "                    is_repeat = False\n",
    "                    break\n",
    "            if is_repeat:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        newstr = s+s\n",
    "        return s in newstr[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "#         # 移动匹配：s in s+s 中\n",
    "#         ss = s + s\n",
    "#         if s in ss[1:-1]:\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "    \n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "#         # kmp解法: s 的最长前后缀相等子串的补就是 最小重复子串\n",
    "\n",
    "#         n = len(s)\n",
    "#         j = self.getNext(s)[-1]\n",
    "#         if n <= 1: return False\n",
    "#         if j != 0 and j % (n-j) == 0:\n",
    "#             return True\n",
    "#         return False\n",
    "\n",
    "\n",
    "#     def getNext(self,s):\n",
    "\n",
    "#         next = [-1,0]\n",
    "#         n = len(s)\n",
    "#         j = 0\n",
    "\n",
    "#         for i in range(1,n):\n",
    "\n",
    "#             while j >0 and s[j] != s[i]:\n",
    "#                 j = next[j]\n",
    "#             if s[j] == s[i]:\n",
    "#                 j += 1\n",
    "#             # 更新next\n",
    "#             next.append(j)\n",
    "#         return next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        \n",
    "        substr = \"\"\n",
    "        for i in range(0, n//2):\n",
    "            if n % (i+1) == 0:\n",
    "                substr = s[:i+1]\n",
    "                if substr * int(n/(i+1))  == s:\n",
    "                    return True\n",
    "                \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "        # 移动匹配：s in s+s 中\n",
    "        ss = s + s\n",
    "        if s in ss[1:-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        par = ''\n",
    "        for i in range(n):\n",
    "            flag = 0\n",
    "            par += s[i]\n",
    "            if n%len(par)!=0:\n",
    "                continue\n",
    "            for j in range(i+1,n):\n",
    "                f = j%len(par)\n",
    "                if s[j]!=par[f]:\n",
    "                    flag =1\n",
    "                    break\n",
    "            if flag==0 and len(par)<n:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def check(substr):\n",
    "            if len(substr) == len(s):\n",
    "                return False\n",
    "            l = len(substr)\n",
    "            if len(s) % l !=0:\n",
    "                return False\n",
    "            ind = 0\n",
    "            while ind+l<=len(s):\n",
    "                if s[ind:ind+l] != s[:l]:\n",
    "                    return False\n",
    "                ind += l\n",
    "            print(\"sub:\", substr)\n",
    "            return True\n",
    "        for i in range(1,len(s)):\n",
    "            if check(s[:i]):\n",
    "                return True\n",
    "            # print(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def kmp(query: str, pattern: str) -> bool:\n",
    "            n, m = len(query), len(pattern)\n",
    "            fail = [-1] * m\n",
    "            for i in range(1, m):\n",
    "                j = fail[i - 1]\n",
    "                while j != -1 and pattern[j + 1] != pattern[i]:\n",
    "                    j = fail[j]\n",
    "                if pattern[j + 1] == pattern[i]:\n",
    "                    fail[i] = j + 1\n",
    "            match = -1\n",
    "            for i in range(1, n - 1):\n",
    "                while match != -1 and pattern[match + 1] != query[i]:\n",
    "                    match = fail[match]\n",
    "                if pattern[match + 1] == query[i]:\n",
    "                    match += 1\n",
    "                    if match == m - 1:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return kmp(s + s, s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        return s in (s+s)[1:-1]\n",
    "        #return s in (s+s)[1:2*len(s)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if n==1:\n",
    "            return False\n",
    "        elif len(set(s))==1:\n",
    "            return True\n",
    "        if n==2:\n",
    "            if s[0]==s[1]:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(1,n):  # n>2的情况\n",
    "            needle=s[:i+1]\n",
    "            sup=s[i+1:]\n",
    "            if len(needle)>len(sup):\n",
    "                break\n",
    "            j=i+1\n",
    "            flag=1 \n",
    "            while j<n:                   \n",
    "                sup1=s[j:j+i+1]\n",
    "                if needle!=sup1:\n",
    "                    flag=0   # 不等的情况\n",
    "                j+=i+1\n",
    "            if flag==1:  # 说明当前这个needle是一个重复子串\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        ans = ''\n",
    "        if len(s)>1:\n",
    "            for i in range(len(s)-1):\n",
    "                ans += s[i]\n",
    "        #         print(ans)\n",
    "                if len(s)%(i+1) == 0:\n",
    "                    if ans * int(len(s)/(i+1)) == s:\n",
    "                        return True\n",
    "                        break\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        subset = ''\n",
    "        for i in range(len(s)):\n",
    "            subset += s[i]\n",
    "            if len(s) % len(subset) == 0 and subset*(len(s)//len(subset)) == s and len(s)/2 >= len(subset):\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 1:\n",
    "            return False\n",
    "        def getpmt(s):\n",
    "            n, j = len(s), 0\n",
    "            ar = [0] * n\n",
    "            for i in range(1, n):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = ar[j - 1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                ar[i] = j\n",
    "            return ar\n",
    "        pmt = getpmt(s)\n",
    "        news = (2 * s)[1:-1]\n",
    "        n, j = len(news), 0\n",
    "        for i in range(n):\n",
    "            while j > 0 and news[i] != s[j]:\n",
    "                j = pmt[j - 1]\n",
    "            if news[i] == s[j]:\n",
    "                j += 1\n",
    "            if j == len(s):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        a = ''\n",
    "        n = 0\n",
    "        for i in range(len(s)):\n",
    "            a += s[i]\n",
    "            if len(s) % len(a) == 0 and len(a) != len(s) and a*( len(s) // len(a) ) == s:\n",
    "                return True\n",
    "        return False    \n",
    "\n",
    "                \n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getNext(self, s: str):\n",
    "        # 后缀匹配指向\n",
    "        i = 0\n",
    "        # 前缀匹配指向\n",
    "        j = -1\n",
    "        # 初始化 next 数组\n",
    "        next = [-1] * len(s)\n",
    "\n",
    "        # 此处 next[0] = -1，所以只需要求剩下的 len(T)-1 个即可\n",
    "        while i < len(s) - 1:\n",
    "            # j == -1 就是找无可找 or 匹配成功，相同前缀长度增加1\n",
    "            if j == -1 or s[i] == s[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                next[i] = j\n",
    "            # 匹配不成功则在前面的子串中继续搜索，直至找不到（即 j== -1 的情况）\n",
    "            else:\n",
    "                j = next[j]\n",
    "\n",
    "        return next\n",
    "\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "\n",
    "        next = self.getNext(s)\n",
    "        n = len(s)\n",
    "        # 最长公共前后缀\n",
    "        maxLen = next[n - 1] + 1\n",
    "\n",
    "        if maxLen == 0 or s[n - 1] != s[n - 1 - maxLen]:\n",
    "            return False\n",
    "\n",
    "        return n % (n - maxLen) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        for i in range(len(s) // 2):\n",
    "            low_s = s[:i + 1]\n",
    "            temp = low_s\n",
    "            while len(low_s) < len(s):\n",
    "                low_s = low_s + temp\n",
    "            if low_s == s:\n",
    "                return True            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        next = [0]*len(s)\n",
    "        self.next(s,next)\n",
    "        if next[-1] != 0 and len(s)%(len(s)-next[-1]) == 0:\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "\n",
    "    def next(self,s,next):\n",
    "        j = 0\n",
    "        next[0] = 0 \n",
    "        for i in range(1,len(s)):\n",
    "            while j>0 and s[i] != s[j]:\n",
    "                j = next[j-1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next[i] = j\n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        nxt = [0] * len(s)\n",
    "        self.getNext(nxt, s)\n",
    "        if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def getNext(self, nxt, s):\n",
    "        nxt[0] = -1\n",
    "        j = -1\n",
    "        for i in range(1, len(s)):\n",
    "            while j >= 0 and s[i] != s[j + 1]:\n",
    "                j = nxt[j]\n",
    "            if s[i] == s[j + 1]:\n",
    "                j += 1\n",
    "            nxt[i] = j\n",
    "        return nxt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        nxt = [0] * len(s)\n",
    "        self.getNext(nxt ,s)\n",
    "        if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "    def getNext(self, nxt, s):\n",
    "        nxt[0] = -1\n",
    "        j = -1\n",
    "        for i in range(1, len(s)):\n",
    "            while j >= 0 and s[i] != s[j+1]:\n",
    "                j = nxt[j]\n",
    "            if s[i] == s[j+1]:\n",
    "                j += 1\n",
    "            nxt[i] = j\n",
    "        return nxt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def kmp(pattern: str) -> bool:\n",
    "            n = len(pattern)\n",
    "            fail = [-1] * n\n",
    "            for i in range(1, n):\n",
    "                j = fail[i - 1]\n",
    "                while j != -1 and pattern[j + 1] != pattern[i]:\n",
    "                    j = fail[j]\n",
    "                if pattern[j + 1] == pattern[i]:\n",
    "                    fail[i] = j + 1\n",
    "            return fail[n - 1] != -1 and n % (n - fail[n - 1] - 1) == 0\n",
    "        \n",
    "        return kmp(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        child_s = \"\"\n",
    "        i = 0\n",
    "        while i*2 < len(s)-1:\n",
    "            child_s += s[i]\n",
    "            if \"\".join(s.split(child_s)) == \"\":\n",
    "                return True\n",
    "            i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def get_next(s:str):\n",
    "            i,j=0,-1\n",
    "            next=[-1]*len(s)\n",
    "            while i<len(s)-1:\n",
    "                if j==-1 or s[i]==s[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                    next[i]=j\n",
    "                else:\n",
    "                    j=next[j]\n",
    "            return next\n",
    "        next=get_next(s)\n",
    "        maxLen=next[len(s)-1]+1\n",
    "        if maxLen==0 or s[len(s)-1]!=s[len(s)-1-maxLen]:\n",
    "            return False\n",
    "        return len(s)%(len(s)-maxLen)==0        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        lens =len(s)\n",
    "        if lens ==0:\n",
    "            return False\n",
    "        nxt = [0]*lens\n",
    "\n",
    "        self.getnext(nxt,s)\n",
    "        if nxt[lens-1] !=  -1 and lens % (lens -(nxt[-1]+1)) ==0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def getnext(self, nxt,s):\n",
    "        nxt[0]=-1\n",
    "        j=-1\n",
    "        for i in range(1,len(s)):\n",
    "            while j>=0 and s[i]!= s[j+1]:\n",
    "                j=nxt[j]\n",
    "            if s[i]==s[j+1]:\n",
    "                j+=1\n",
    "                \n",
    "            nxt[i]=j\n",
    "\n",
    "        return nxt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def kmp(pattern: str) -> bool:\n",
    "            n = len(pattern)\n",
    "            fail = [-1] * n\n",
    "            for i in range(1, n):\n",
    "                j = fail[i - 1]\n",
    "                while j != -1 and pattern[j + 1] != pattern[i]:\n",
    "                    j = fail[j]\n",
    "                if pattern[j + 1] == pattern[i]:\n",
    "                    fail[i] = j + 1\n",
    "            return fail[n - 1] != -1 and n % (n - fail[n - 1] - 1) == 0\n",
    "        \n",
    "        return kmp(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n =len(s)\n",
    "        j = 0\n",
    "        nextIndex = [0] * n\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nextIndex[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            nextIndex[i] = j\n",
    "        # print(nextIndex[-1])\n",
    "        return nextIndex[-1] != 0 and n % (n - nextIndex[-1]) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        # #穷举\n",
    "        # n=len(s)\n",
    "        # for i in range(1,n//2+1):\n",
    "        #     if(n%i==0):\n",
    "        #         t=s[0:i]\n",
    "        #         start=0\n",
    "        #         while(start<n):\n",
    "        #             k=0\n",
    "        #             while(k<i):\n",
    "        #                 if(t[k]!=s[start+k]):\n",
    "        #                     break\n",
    "        #                 k+=1\n",
    "        #             if(k!=i):\n",
    "        #                 break\n",
    "        #             start+=i\n",
    "        #         if(start==n):\n",
    "        #             return True\n",
    "        # return False \n",
    "\n",
    "        #kmp\n",
    "        def compute_lps(s):\n",
    "            m=len(s)\n",
    "            lps=[0]*m\n",
    "            k=0\n",
    "            for i in range(1,m):\n",
    "                while(k>0 and s[k]!=s[i]):\n",
    "                    k=lps[k-1]\n",
    "                if(s[k]==s[i]):\n",
    "                    lps[i]=k+1\n",
    "                    k+=1\n",
    "            return lps\n",
    "        \n",
    "        n=len(s)\n",
    "        lps=compute_lps(s)\n",
    "        return True if(lps[-1]!=0 and n%(n-lps[-1])==0) else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        next = [0] * len(s)     # 初始化前缀表next\n",
    "        j = 0       # 初始化最长相等前后缀长度\n",
    "\n",
    "        for i in range(1, len(s)):      # 获取前缀表next\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = next[j - 1]     # 若i和j对应的s元素不相同，则j回退到next[j - 1]代表的位置\n",
    "            if s[i] == s[j]:\n",
    "                j += 1      # 若i和j对应的s元素相同，则i和j均+1，注意对于每一个i，j只可能有一次+1操作，但可能有很多次回退操作\n",
    "            next[i] = j     # j的取值即为当前i位置的前缀表的元素值\n",
    "        \n",
    "        \"\"\"\n",
    "            首先判断next的最后一个元素不为0，如果为0则一定不重复\n",
    "            其次，如果字符串s重复，则next的最大值一定取到最后一个元素位置，所以使用len(s) - next[-1]\n",
    "        \"\"\"\n",
    "        if next[-1] != 0 and len(s) % (len(s) - next[-1] ) == 0:      # 判断字符串是否重复，这里不能是len(s) - max(next)，否则可能会出现6 % 2和6 % 3都能整除，导致判断错误  \n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        def kmp(pattern: str) -> bool:\n",
    "            n = len(pattern)\n",
    "            fail = [-1] * n\n",
    "            for i in range(1, n):\n",
    "                j = fail[i - 1]\n",
    "                while j != -1 and pattern[j + 1] != pattern[i]:\n",
    "                    j = fail[j]\n",
    "                if pattern[j + 1] == pattern[i]:\n",
    "                    fail[i] = j + 1\n",
    "            return fail[n - 1] != -1 and n % (n - fail[n - 1] - 1) == 0\n",
    "        \n",
    "        return kmp(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        next = [0] * len(s)\n",
    "        self.getNext(next, s)\n",
    "        if next[-1] != 0 and len(s) % (len(s) - next[-1]) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getNext(self, next, s):\n",
    "        j = 0\n",
    "        next[0] = 0\n",
    "        for i in range(1, len(s)):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = next[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next[i] = j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        next = [0] * len(s)\n",
    "        self.getnext(next, s)\n",
    "        if next[-1] != 0 and len(s) % (len(s) - next[-1]) == 0:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def getnext(self, next, s):\n",
    "        next[0] = 0\n",
    "        j = 0\n",
    "        for i in range(1,len(s)):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = next[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            next[i] = j\n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        ################ kmp算法 #################\n",
    "        # def kmp(T, p):\n",
    "        #     m, n = len(p), len(T)\n",
    "        #     next = [0] * m\n",
    "        #     left = 0\n",
    "        #     for right in range(1, m):\n",
    "        #         while left > 0 and p[left] != p[right]:\n",
    "        #             left = next[left - 1]\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #         next[right] = left\n",
    "\n",
    "        #     j = 0\n",
    "        #     for i in range(1, n-1):\n",
    "        #         while j > 0 and T[i] != p[j]:\n",
    "        #             j = next[j - 1]\n",
    "        #         if T[i] == p[j]:\n",
    "        #             j += 1\n",
    "        #         if j == m:\n",
    "        #             return True\n",
    "        #     return False\n",
    "        # return kmp(s + s, s)\n",
    "\n",
    "        ################ 枚举法 #################\n",
    "        # n = len(s)\n",
    "        # for i in range(1, n //2 + 1):\n",
    "        #     if n % i == 0:\n",
    "        #         if all(s[j] == s[j - i] for j in range(i, n)):\n",
    "        #             return True\n",
    "        # return False\n",
    "\n",
    "        ################ 内置函数的字符串匹配 #################\n",
    "        # return (s + s).find(s, 1) != len(s)\n",
    "        # 这种思想借助了一个证明，两个s拼接后，如果在排除开头和结尾字符的子串上包含s，那么这个s一定是由多个子串重复组成的\n",
    "\n",
    "        ################ 利用上述结论改进kmp算法 #################\n",
    "        def kmp(p):\n",
    "            m, left = len(p), 0\n",
    "            next = [0] * m\n",
    "            for right in range(1, m):\n",
    "                while left > 0 and p[right] != p[left]:\n",
    "                    left = next[left - 1]\n",
    "                if p[left] == p[right]:\n",
    "                    left += 1\n",
    "                next[right] = left\n",
    "            \n",
    "            return next[m - 1] != 0 and m % (m - next[m - 1]) == 0 \n",
    "        return kmp(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "#         # 移动匹配：s in s+s 中\n",
    "#         ss = s + s\n",
    "#         if s in ss[1:-1]:\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "\n",
    "        # kmp解法: s 的最长前后缀相等子串的补就是 最小重复子串\n",
    "\n",
    "        n = len(s)\n",
    "        j = self.getNext(s)[-1]\n",
    "        if n <= 1: return False\n",
    "        if j != 0 and j % (n-j) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getNext(self,s):\n",
    "\n",
    "        next = [-1,0]\n",
    "        n = len(s)\n",
    "        j = 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            while j >0 and s[j] != s[i]:\n",
    "                j = next[j]\n",
    "            if s[j] == s[i]:\n",
    "                j += 1\n",
    "            # 更新next\n",
    "            next.append(j)\n",
    "        return next\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        ################ kmp算法 #################\n",
    "        # def kmp(T, p):\n",
    "        #     m, n = len(p), len(T)\n",
    "        #     next = [0] * m\n",
    "        #     left = 0\n",
    "        #     for right in range(1, m):\n",
    "        #         while left > 0 and p[left] != p[right]:\n",
    "        #             left = next[left - 1]\n",
    "        #         if s[left] == s[right]:\n",
    "        #             left += 1\n",
    "        #         next[right] = left\n",
    "\n",
    "        #     j = 0\n",
    "        #     for i in range(1, n-1):\n",
    "        #         while j > 0 and T[i] != p[j]:\n",
    "        #             j = next[j - 1]\n",
    "        #         if T[i] == p[j]:\n",
    "        #             j += 1\n",
    "        #         if j == m:\n",
    "        #             return True\n",
    "        #     return False\n",
    "        # return kmp(s + s, s)\n",
    "\n",
    "        ################ 枚举法 #################\n",
    "        # n = len(s)\n",
    "        # for i in range(1, n //2 + 1):\n",
    "        #     if n % i == 0:\n",
    "        #         if all(s[j] == s[j - i] for j in range(i, n)):\n",
    "        #             return True\n",
    "        # return False\n",
    "\n",
    "        ################ 内置函数的字符串匹配 #################\n",
    "        # return (s + s).find(s, 1) != len(s)\n",
    "        # 这种思想借助了一个证明，两个s拼接后，如果在排除开头和结尾字符的子串上包含s，那么这个s一定是由多个子串重复组成的\n",
    "\n",
    "        ################ 利用上述结论改进kmp算法 #################\n",
    "        def kmp(p):\n",
    "            m, left = len(p), 0\n",
    "            next = [0] * m\n",
    "            for right in range(1, m):\n",
    "                while left > 0 and p[right] != p[left]:\n",
    "                    left = next[left - 1]\n",
    "                if p[left] == p[right]:\n",
    "                    left += 1\n",
    "                next[right] = left\n",
    "            \n",
    "            return next[m - 1] != 0 and m % (m - next[m - 1]) == 0 \n",
    "        return kmp(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\r\n",
    "        if len(s) == 1:\r\n",
    "            return False\r\n",
    "        i,j = 1,0\r\n",
    "        next = [0]*len(s)\r\n",
    "        while i < len(s):\r\n",
    "            if s[i] == s[j]:\r\n",
    "                next[i] = j+1\r\n",
    "                i += 1\r\n",
    "                j += 1\r\n",
    "            else:\r\n",
    "                if j == 0:\r\n",
    "                    next[i] = 0 \r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    j = next[j-1]\r\n",
    "        # print(next)\r\n",
    "        if next[-1]>0:\r\n",
    "            sub_len = len(s)-next[-1]\r\n",
    "            cnt = len(s)//sub_len\r\n",
    "            # print(sub_len,cnt)\r\n",
    "            if s[0:sub_len]*cnt == s:\r\n",
    "                return True \r\n",
    "        return False\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        child_s = \"\"\n",
    "        for i in range(n//2):\n",
    "            child_s += s[i]\n",
    "            if \"\".join(s.split(child_s)) == \"\":\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:\n",
    "        n =len(s)\n",
    "        j = 0\n",
    "        nextIndex = [0] * n\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and s[i] != s[j]:\n",
    "                j = nextIndex[j - 1]\n",
    "            if s[i] == s[j]:\n",
    "                j += 1\n",
    "            nextIndex[i] = j\n",
    "        # print(nextIndex[-1])\n",
    "        return nextIndex[-1] != 0 and n % (n - nextIndex[-1]) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def repeatedSubstringPattern(self, s: str) -> bool:  \n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        nxt = [0] * len(s)\n",
    "        self.getNext(nxt, s)\n",
    "        if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def getNext(self, nxt, s):\n",
    "        nxt[0] = -1\n",
    "        j = -1\n",
    "        for i in range(1, len(s)):\n",
    "            while j >= 0 and s[i] != s[j+1]:\n",
    "                j = nxt[j]\n",
    "            if s[i] == s[j+1]:\n",
    "                j += 1\n",
    "            nxt[i] = j\n",
    "        return nxt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
